1. Field of the Invention
The invention pertains to methods and apparatus for generation of color video images from computers. More specifically, the invention pertains to methods and apparatus for generation of real-time raster-scanned color graphics from computer-generated instructions comprising multiple polygons making up a video image.
2. Description of the Prior Art
The idea of storing an image in computer memory and repeatedly "refreshing" (updating) the raster display by scanning the stored image was originally introduced by Noll in 1971. Since then stored image or "frame buffer" (computer memory storing an entire video screen image) systems attached to television-like raster color displays have dominated the field of computer graphics. Such graphics are used in such applications as video games, computer added design, and computer simulation for pilot training and the like.
An image may be composed of a plurality of polygons. In many applications of computer graphics, such as real-time simulation applications, a large number of polygons is needed to represent a realistic image. An application program running on the main, or "host" computer will compute the location, shape, and color of each polygon in the image. Each polygon is composed of several "pixels" (picture elements--the smallest addressable image unit of the screen-one dot). Display procedures running on the display processor will "paint" (fill with color) all pixels within a given polygon into the frame buffer. On a typical 512.times.512 (512 lines by 512 pixels) frame buffer, "background painting" (filling the entire screen with a single color) requires 262,144 pixel store operations into the frame buffer plus a similar number of overhead looping operations. Therefore, it is well-known in the art to use a special purpose display processor to unload the large number of simple "pixel operations" (storing a color into a storage location representing a picture element) from the general purpose host computer.
A typical prior art display processor (4) with frame buffer memory (5) & (5a) is shown in FIG. 7. The host (1) is connected to the display processor through I/O processors (2). In a programming environment communication between the host (1) and the terminal (3) is performed by a sequence of characters. Similarly, in a graphics environment communication between the host (1) and the display processor (4) is performed by a sequence of polygon commands. Each polygon command can be interpreted by the image processor (4) to call one of the display porcedures with the proper parameters such as color and size. Note that points, lines, triangles, rectangles and trapezoids can be painted using polygon commands.
While the image processor (4) is painting polygons into the frame buffer (5), the refresh circuitry (16) is periodically refreshing the raster display (7) by scanning across each row of the frame buffer (5) and reading the color stored at each pixel location. Periodic display refreshing at 30 frames per second (a minimum for "real time" image generation without flicker) requires a constant 512.times.512.times.30=7,864,320 frame buffer read operations per second. Additional frame buffer bandwidth is required for image generation or painting. Since the frame buffer (5) may be simultaneously requested by the image processor (4) and the refresh circuitry (6), shared memory access contentions should be resolved by synchronization of the two processes or by giving the refresh circuitry top priority. Some systems add a second frame buffer (5a), identical with the first, to allow video refresh from one buffer while the image processor is updating the other. Additionally, a "Z-Buffer" (9), giving the depth of any point in the frame buffer, may be provided for hidden-surface removal.
The programmer looks at the display processor system as a special purpose peripheral. As described above, the functional behavior of the frame buffer can be easily understood. The programmer is expected to build and maintain several polygon lists for a specific application. An interactive program will then respond to user inputs by updating polygon lists and sending parts of each polygon list to the display processor. The polygons will then appear on the screen after a finite image updating delay.
All display processors support a set of polygon painting commands, just as microcomputers support a set of basic instructions. Therefore the main performance index for differentiating among various classes of display processors is the typical image updating delay, which is the time from sending of polygons to the display processor to the time that the polygons are fully displayed on the screen. For typical images the image updating delay may range from a few minutes to several seconds depending on the system hardware. An image stored in the frame buffer (5) will be displayed for several refresh periods. After observing the image for some time, the user may request that portions of the present image be updated or a new image be generated.
Contrary to common belief, frame buffer memory design is not an easy problem which can be cured in time by increase in capacity and decrease in cost of standard MOS memories. The frame buffer memory in present commercial systems may be as complex as a 512.times.512 orthogonally structured skew interleaved boundary aligned time multiplexed shared static random access memory with effective memory bandwidth in excess of 8 MHz. Image regeneration of such systems may last for several seconds. Many dynamic or real time applications cannot tolerate such long delays. Several special purpose architectures have been developed to speed up the image generation process.
There is a present need for real time color image generations. Viewing operations, such as coordinate translation and rotation, are fundamental to interactive computer graphics. In the specific case of designing VLSI circuits, the image of the circuit on the screen is a small window for viewing part of a much larger layout of several thousand transistors and other electrical devices. The designer may want to scroll in various directions with the same viewing window in order to follow connections to other parts of the circuit. Other common editing operations such as deleting a piece of the layout, dragging an object across the screen and making incremental changes to the image generally require image regeneration and may last for several seconds. Given that the designer has to deal with several thousand transitors, such unnecessary delays can become frustrating. Real time systems can perform such operations immediately and without any delay. Video games also require immediate response to the user inputs. Frame buffer systems are generally too slow and expensive for such dynamic and popular applications. More advanced systems for flight simulation require real time image generation for causing an illusion of motion in real life environments. Although vector systems (using a special display drawing point-to-point lines to create images, in place of the TV-like raster) can perform dynamic operations by regenerating the vector image at 30 frames/sec, it is highly desirable to achieve similar performance on raster color systems. The general cure to all of the above (and even more) problems is regeneration of raster color image at 30 frames/sec. Therefore, it is an object of the invention to provide special purpose hardware that can generate real time (30 frames per second or better) color images.
For a prior art enhanced frame-buffer system, see Sukonick, et al., U.S. Pat. No. 4,197,590 (1980).
Several image synthesis and analysis problems can be solved by performing simple computations at every pixel in the image. However, the large number of computations can cause long and intolerable delays. The computation time can be reduced by employing several processors to simultaneously operate on parts of the image. A possible solution is to have an array of simple processors with a processor for every pixel in the image. Like other architectures, a special purpose control processor will issue data and simple instructions to each row and column of the pixel processor array. Pixel Planes designed by Fuchs and Poulton ("Pixel-Planes: A VLSI-Oriented Design for a Raster Graphics Engine", VLSI-Design, third quarter 1981) is a member of the processor per pixel family. Whelan ("A Rectangular Area Filling Display System Architecture", Computer Graphics, July 1982) has also designed a rectangular area filling system which paints rectangles by selecting a range of rows and columns of the image. Each processor will then paint its pixel if both its row and column lines are selected. These architectures attempt to paint all pixels within a polygon or rectangle in one operation cycle.
In addition to simple pixel painting, hidden surface removal by depth and polygon color shading require computations at every pixel location. With processor per pixel architectures, one can perform such computationally intensive operations by increasing the complexity of each pixel processor without any sacrifice in overall system speed and performance.
Although the idea of having a processor per pixel is a desirable solution for the image generation problem, implementation of a 512.times.512 pixel processor array is simply too large to be practical. Those familiar with parallel processing are aware of several classical designs which have failed mainly due to underestimation of overall system size and cost.
It is therefore an object of the invention to provide a real-time color graphics display processing system without the requirement for complex one-processor-per-pixel systems.
Multiprocessor schemes attempt to achieve speed by painting several pixels from a given polygon in each operation cycle. The goal is minimization of the time required for painting each individual polygon.
Since a frame is composed of several polygons, one should ultimately attempt to achieve real time performance by painting several pixels from several polygons in each operation cycle. The goal is reduction of the time required for painting each frame to less than 33 milliseconds. One may then exploit the larger parallelism in this problem to systematically build an array of processors which can generate real time images.